package com.hdu.other.dp.shuweiDp;




public class lc2376 {
    class Solution {
        public int countSpecialNumbers(int n) {
            int len = 1;
            int offset = 1;
            int tmp = n / 10;
            while (tmp > 0) {
                len++;
                offset *= 10;
                tmp /= 10;
            }
            int ans = 0;
            if (len >= 2) {
                ans = 9;
                for (int i = 2, a = 9, b = 9; i < len; i++, b--) {
                    a *= b;
                    ans += a;
                }
            }
            int[] cnt = new int[len];
            cnt[0] = 1;
            for (int i = 1, k = 10 - len + 1; i < len; i++, k++) {
                cnt[i] = cnt[i - 1] * k;
            }
            int first = n / offset;
            ans += (first - 1) * cnt[len - 1];
            ans += f(n, len - 1, offset / 10, cnt, 1 << first);
            return ans;
        }

        int f(int n, int len, int offset, int[] cnt, int status) {
            if (len == 0)
                return 1;

            int cur = (n / offset) % 10;
            int ans = 0;
            for (int i = 0; i < cur; i++)
                if ((status & (1 << i)) == 0)
                    ans += cnt[len - 1];
            if ((status & (1 << cur)) == 0)
                ans += f(n, len - 1, offset / 10, cnt, status | (1 << cur));
            return ans;
        }
    }
}
